/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-06-15
 * Time: 21:12
 */
public class Main {
    public int uniquePaths(int m, int n) {

        //1. 建立dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
    public int uniquePathsWithObstacles(int[][] o) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值

        int m = o.length;
        int n = o[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                dp[i][j] = o[i - 1][j - 1] == 0 ? dp[i][j - 1] + dp[i - 1][j] : 0;
            }
        }
        return dp[m][n];
    }
    public int maxValue(int[][] grid) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
    public int minFallingPathSum(int[][] matrix) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int m = matrix.length;
        int n = matrix.length;
        int[][] dp = new int[m + 1][n + 2];
        for(int i = 1; i < m + 1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = 1; i < n + 1; i++) {
            min = Math.min(min, dp[m][i]);
        }
        return min;
    }
    public int minPathSum(int[][] grid) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值

        int m = grid.length;
        int n = grid[0].length;
        int dp[][] = new int[m + 1][n + 1];
        for(int i = 0; i < m + 1; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for(int j = 0; j < n + 1; j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = 0;
        dp[m - 1][n] = 0;
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }
        return dp[0][0];
    }
    public int calculateMinimumHP(int[][] dungeon) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0; i < m + 1; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for(int j = 0; j < n + 1; j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1,
                        Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }

}
